Computation of the discrete Fourier transform (DFT) is important in many signal processing applications such as radar processing, spectrum analysis, materials analysis, orthogonal frequency division multiplexing (OFDM), radio astronomy and other applications requiring high data rate DFT computation. The Fourier transform is, in general, a central component in many signal analysis systems. Due to its importance, a wide variety of DFT implementations for general purpose computers, digital signal processors, VLSI circuits and programmable hardware have been developed.
The fast Fourier transform (FFT) is the standard method for computing the DFT. Pipeline implementations have been developed which include a series of computational blocks, each block composed of delay lines, coefficient storage, commutators, multipliers, and adders. In these existing pipeline implementations, the number of delay lines and coefficient storage increases linearly with the size of the transform. Other implementations, including systems using multi-port memories and special address generators to properly order the inputs, and approaches that attempt to gain parallelism in hardware, have also been developed.